package com.cdream.basic.algorithm.leetcode.dfs;

import java.util.ArrayList;

/**
 * @author cdream
 * @date 8/16/21
 */
public class Question526 {
    private int count = 0;
    private ArrayList<Integer> list = new ArrayList<>();
    private boolean[] used;
    public int countArrangement(int n) {
        used = new boolean[n+1];
        dfs(n);
        return count;
    }

    public void dfs(int n){
        if(list.size()==n && (list.get(n-1) % n ==0 || n % list.get(n-1)==0)){
            count++;
            return;
        }
        for(int i = 1; i<=n; i++){
            if(used[i]){
                continue;
            }
            int l = list.size();
            if(i % (l+1) ==0 || (l+1) % i==0){
                list.add(i);
                used[i] = true;
                dfs(n);
                list.remove(list.size()-1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Question526().countArrangement(15));
    }
}
